from typing import List


class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        # 邻接矩阵
        path = []
        res = []

        def dfs(n):
            if n == len(graph)-1:
                # 输入的节点等于最后一个节点-> 终止
                res.append(path.copy())# 别忘了copy
                return

            for i in graph[n]:
                path.append(i)
                dfs(i)
                # 回溯
                path.pop()

        path.append(0)
        dfs(0)

        return res